#include <bits/stdc++.h>
using namespace std;

/*
808. 分汤
已解答
中等
相关标签
premium lock icon
相关企业
你有两种汤，A 和 B，每种初始为 n 毫升。在每一轮中，会随机选择以下四种服务操作中的一种，每种操作的概率为 0.25，且与之前的所有轮次 无关：

从汤 A 取 100 毫升，从汤 B 取 0 毫升
从汤 A 取 75 毫升，从汤 B 取 25 毫升
从汤 A 取 50 毫升，从汤 B 取 50 毫升
从汤 A 取 25 毫升，从汤 B 取 75 毫升
注意：

不存在先分配 100 ml 汤B 的操作。
汤 A 和 B 在每次操作中同时被倒入。
如果一次操作要求你倒出比剩余的汤更多的量，请倒出该汤剩余的所有部分。
操作过程在任何回合中任一汤被用完后立即停止。

返回汤 A 在 B 前耗尽的概率，加上两种汤在 同一回合 耗尽概率的一半。返回值在正确答案 10-5 的范围内将被认为是正确的。

 

示例 1:

输入：n = 50
输出：0.62500
解释：
如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
示例 2:

输入：n = 100
输出：0.71875
解释：
如果我们选择第一个操作，A 首先将变为空。
如果我们选择第二个操作，A 将在执行操作 [1, 2, 3] 时变为空，然后 A 和 B 在执行操作 4 时同时变空。
如果我们选择第三个操作，A 将在执行操作 [1, 2] 时变为空，然后 A 和 B 在执行操作 3 时同时变空。
如果我们选择第四个操作，A 将在执行操作 1 时变为空，然后 A 和 B 在执行操作 2 时同时变空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.71875。
 

提示:

0 <= n <= 109
*/

// 法一
class Solution {
public:
    double soupServings(int n) {
        if (n == 0) return 0.5;

        // 毫升向上取整 25一个单位
        int k = (n + 24) / 25;
        // n-->max. A先耗尽 --> 1
        if (k >= 200)   return 1.0;

        // dp[i][j]    A剩i B剩j 的目标概率
        vector<vector<double>> dp(k + 1, vector<double>(k + 1, 0.0));

        // 边界处理
        dp[0][0] = 0.5;
        for (int j = 1; j <= k; j++)    dp[0][j] = 1;   // A耗尽
        for (int i = 1; i <= k; i++)    dp[i][0] = 1;   // B耗尽 不符合

        // 填充dp表
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= k; j++) {
                // 四种操作概率都一样
                double prob = 0;
                // 操作1: A减4单位，B减0
                int a1 = i - 4, b1 = j;
                prob += getProb(a1, b1, dp);
                
                // 操作2: A减3，B减1
                int a2 = i - 3, b2 = j - 1;
                prob += getProb(a2, b2, dp);
                
                // 操作3: A减2，B减2
                int a3 = i - 2, b3 = j - 2;
                prob += getProb(a3, b3, dp);
                
                // 操作4: A减1，B减3
                int a4 = i - 1, b4 = j - 3;
                prob += getProb(a4, b4, dp);
                
                dp[i][j] = 0.25 * prob;
            }
        }
        return dp[k][k];
    }

    double getProb(int a, int b, const vector<vector<double>>& dp) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
        return dp[a][b];
    }
};

// 法二
class Solution {
public:
    // 计算汤A和汤B都喝完的概率
    double soupServings(int n) {
        // 利用精度为10^-5，当n大于4800时，概率近似为1
        if (n > 4800) {
            return 1;
        }

        // 将n向上取整到25的倍数，因为每次操作减少的量是25的倍数
        n = ceil((double)n / 25); // 等同于 (n + 24) / 25

        // 初始化记忆化数组，memo[a][b] 表示汤A剩余量为a，汤B剩余量为b时的概率
        vector<vector<double>> memo(n + 1, vector<double>(n + 1, -1));

        // 定义深度优先搜索函数
        function<double(int, int)> dfs = [&](int a, int b) -> double {
            // 如果汤A或汤B的剩余量小于等于0
            if (a <= 0 || b <= 0) {
                // 如果两者都为0，返回0.5，否则如果汤A先喝完返回1，汤B先喝完返回0
                return a == b? 0.5 : a < b;
            }

            // 从记忆化数组中获取结果，如果已经计算过则直接返回
            auto& res = memo[a][b];
            if (res != -1) {
                return res;
            }

            // 四种操作，每种操作的概率为0.25，递归计算所有可能情况的概率并累加
            return res = 0.25 * (dfs(a - 4, b) + dfs(a - 3, b - 1) + dfs(a - 2, b - 2) + dfs(a - 1, b - 3));
        };

        // 从初始状态 (n, n) 开始进行深度优先搜索
        return dfs(n, n);
    }
};